/*
https://leetcode-cn.com/problems/erect-the-fence/solution/an-zhuang-zha-lan-by-leetcode/
 */
import java.util.Arrays;
import java.util.Stack;

public class Solution587 {
    public int[][] outerTrees(int[][] trees) {
        if (trees.length==1){
            return trees;
        }
        int[] start=trees[0];
        for (int i=1;i<trees.length;i++){
            if (trees[i][1]<start[1]){
                start=trees[i];
            }
        }
        int[] finalStart = start;
        Arrays.sort(trees,(a, b)->{
            double diff=orient(finalStart,a,b)-orient(finalStart,b,a);
            if (diff==0){
                return distance(finalStart,a)-distance(finalStart,b);
            }else {
                return diff>0?1:-1;
            }
        });
        int i = trees.length - 1;
        while (i >= 0 && orient(start, trees[trees.length - 1], trees[i]) == 0) {
            i--;
        }
        for (int l = i + 1, h = trees.length - 1; l < h; l++, h--) {
            int[] temp = trees[l];
            trees[l] = trees[h];
            trees[h] = temp;
        }
        Stack<int[]> stack = new Stack<>();
        stack.push(trees[0]);
        stack.push(trees[1]);
        for (int j = 2; j < trees.length; j++) {
            int[] top = stack.pop();
            while (orient(stack.peek(), top, trees[j]) > 0) {
                top = stack.pop();
            }
            stack.push(top);
            stack.push(trees[j]);
        }
        int[][] res = new int[stack.size()][2];
        int index = 0;
        for (int[] tree : stack) {
            res[index] = tree;
            index++;
        }
        return res;
    }

    double orient(int[] m,int[] a,int[] b){
        return (a[1]-m[1])*(b[0]-m[0])-(a[0]-m[0])*(b[1]-m[1]);
    }

    int distance(int[] m,int[] n){
        return (m[0]-n[0])*(m[0]-n[0])+(m[1]-n[1])*(m[1]-n[1]);
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new Solution587().outerTrees(new int[][]{{1, 1}, {2, 2}, {2, 0}, {2, 4}, {3, 3}, {4, 2}})));
    }
}
